#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>
typedef struct cust
{
	int arv_t, amount, dur_t;
	struct cust *next;
};
typedef struct ATM
{
	int num;
	cust *head, *tail;
};
typedef struct ev
{
	int time, type; //0 is arrive 1 is depart
	struct ev *next;
};
// 事件表
ev *evlist, *now;
// 两个柜台
ATM bar[2];
// 每次处理的事件
ev *e;
// 总时间 总人数 总金额
int total_time, total_count, total_money;
// 结束时间
const int close_time = 100;
// 随机函数

int rand_(int seed_)
{
	time_t t = time(NULL);
	srand(t);
	return rand() % seed_;
}
// 初始化事件表
void inital()
{
	// 初始化 事件表 evlist
	evlist = (ev *)malloc(sizeof(ev));
	evlist->next = NULL;
	ev *start = (ev *)malloc(sizeof(ev));
	start->next = evlist->next;
	evlist->next = start;
	start->type = 0;
	start->time = 0;
	// now = start;
	// 初始化柜台
	for (int i = 0; i < 2; i++)
	{
		bar[i].num = 0;
		cust *node = (cust *)malloc(sizeof(cust));
		node->next = NULL;
		bar[i].head = bar[i].tail = node;
	}

	// 初始化
	total_time = total_count = 0;
	total_money = 1000;
}
// 出队
void pop(ATM &bar_no)
{
	// dp_cust是最后一个节点
	if (bar_no.num == 1)
	{
		bar[1].head->next = NULL;
		bar[1].tail = bar[1].head;
	}
	// 若不是是最后一个节点
	else
	{
		bar[1].head->next = bar[1].head->next->next;
	}
	bar[1].num--;
}
// 插入一个事件到有序事件表中
void insert(ev *even)
{
	ev *p = evlist;

	while (p->next && even->time > p->next->time)
	{
		p = p->next;
	}
	even->next = p->next;
	p->next = even;
}
// 生成下一个到达的客户
void next_arv()
{
	int next = rand_(13);
	if (e->time + next <= close_time)
	{
		ev *arv = (ev *)malloc(sizeof(ev));
		arv->time = e->time + next;
		arv->type = 0;
		arv->next = NULL;
		insert(arv);
	}
}
// 处理用户时间 把用户离开事件加入事件表
void deal_dpt(cust *customer)
{
	customer->dur_t = rand_(20) + 5;
	customer->amount = rand_(1000) - 500;
	ev *dp_ev = (ev *)malloc(sizeof(ev));
	dp_ev->type = 1;
	dp_ev->time = e->time + customer->dur_t;
	if (dp_ev->time < close_time)
		insert(dp_ev);
	else
	{
		pop(bar[1]);
		total_time += e->time - customer->arv_t;
	}
}
// 处理到达事件
void arrive()
{
	// 生成下一个顾客到达事件 加入到事件表
	next_arv();
	// 生成一个顾客 要么开始处理事件 要么排队
	cust *customer = (cust *)malloc(sizeof(cust));
	customer->arv_t = e->time;
	++total_count;
	// 加入到队列中
	bar[1].tail->next = customer;
	bar[1].tail = customer;
	bar[1].num++;
	printf("customer arrive:%d time:%d\n", total_count, e->time);
	if (bar[1].num == 1)
		deal_dpt(customer);
}
// 处理离开事件
// 前一个顾客离开 着手下一个顾客的事务
void depart()
{
	// 顾客出队
	cust *dp_cust = bar[1].head->next;
	printf("customer depart time %d\n", e->time);
	// dp_cust是最后一个节点
	pop(bar[1]);
	total_time += (e->time - dp_cust->arv_t);
	if (total_money + dp_cust->amount > 0)
	{
		// 金额变大
		int temp_money = total_money;
		total_money += dp_cust->amount;
		if (temp_money < total_money)
		{
			// 处理队列2中的用户 并让他们离开
			cust *p = bar[0].head->next;
			cust *pre = bar[0].head;
			while (p)
			{
				if (p->amount + total_money >= 0)
				{
					total_money += p->amount;
					// 计算当前用户停留时间
					total_time += (e->time - p->arv_t);
					// 用户出队
					pre->next = p->next;
					// 如果p是队尾元素 尾指针指向 pre
					if (p->next = NULL)
					{
						bar[0].tail = pre;
						break;
					}
				}
				pre = p;
				p = p->next;
			}
		}
	}
	else
	{
		// 把dp_cust 加入队列二
		dp_cust->next = NULL;
		bar[0].tail->next = dp_cust;
		bar[0].tail = dp_cust;
		bar[0].num++;
	}
	// 开始处理下一个用户 把他加入事件表
	if (bar[1].num >= 0)
	{
		cust *customer = bar[1].head->next;
		deal_dpt(customer);
	}
}

// 银行离散事件模拟
void bank()
{
	inital();
	while (evlist->next)
	{
		e = evlist->next;
		evlist->next = e->next;
		Sleep(rand_(500) + 500);
		if (e->type == 0)
			arrive();
		else
			depart();
	}
	if (bar[0].num > 0)
	{
		cust *p = bar[0].head->next;
		while (p)
		{
			total_time += (close_time - p->arv_t);
			p = p->next;
		}
	}
	printf("total:time:%d:custmoer:%d", total_time, total_count);
}

int main()
{
	/*******************code*******************/
	bank();
	/******************************************/
	printf("\n\n****************************\n");
	printf("Press Enter key to continue\n");
	getchar();
	return 0;
	/******************************************/
}
